package com.gxc.array;

import java.util.Stack;

/**
 * 可见山峰对数量
 * 一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。
 * 比如，{3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,3,5}都代表同样结构的环形山。
 * 3 → 1 → 2 → 4 → 5 → 3方向叫作next方向(逆时针)，
 * 3 → 5 → 4 → 2 → 1 → 3方向叫作last方向(时针)，
 *
 * 山峰A和山峰B能够相互看见的条件为:
 * 如果A和B是同一座山，认为不能相互看见。
 * 如果A和B是不同的山，并且在环中相邻，认为可以相互看见。
 * 比如上图中，相邻的山峰对有(1,2)(2,4)(4,5)(3,5)(1,3)。
 * 如果A和B是不同的山，并且在环中不相部，假设两座山高度的最小值为min，
 * 如果A通过next方向到B的途中没有高度比min大的山峰，
 * 或者A通过last方向到B的途中没有高度比min大的山峰，认为A和B可以相互看见。
 * 比上图中，高度为3的山和高度为4的山，两座山的高度最小值为3。3从last方向走向4，
 * 中途会遇见5，所以a方向走不通；3从next方向走向4，中途会遇见1和2，
 * 但是都不大于两座山高度的最小值3，所以next方向可以走通。
 * 有一个能走通就认为可以相互看见。再如，高度为2的山和高度为5的山，两个方向上都走不通，
 * 所以不能相互看见。入上图中所有在环中不相邻，并且能看见的山峰对有(2，3)(3，4)。
 * 给定一个不含有负数且没有重复值的数组arr，请返回有多少对山峰能够相互看见。
 * 进阶问题:给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。
 *
 * 要求
 * 如果arr长度为N，没有重复值的情况下的时间复杂度达到O(1)，
 * 可能有重复值的情况下的时间复杂度请达到O(N)。
 */
public class GetVisibleNum {

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 4, 5};
        System.out.println(handleWithNoRepeat(arr));

        int[] arr2 = {5, 4, 4, 2, 4, 5, 3, 4, 5, 2, 5};
        System.out.println(handleWithRepeat(arr2));
    }

    private static int handleWithNoRepeat(int[] arr) {
        if (arr.length<1) return 0;
        if (arr.length == 2) return 1;
        int sum = 0;

        sum = 2 * (arr.length - 2) +1;
        return sum;
    }

    private static int handleWithRepeat(int[] arr) {
        if (arr.length<2) return 0;
        if (arr.length == 2) return 1;
        int sum = 0;

        //先筛选最大的山峰索引
        int maxIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            maxIndex = arr[i]>arr[maxIndex] ? i: maxIndex;
        }

        Stack<Mountain> stack = new Stack<>();

        stack.push(new Mountain(arr[maxIndex], 1));
        int i = maxIndex+1 == arr.length?0:maxIndex+1;
        while (i!=maxIndex) {
            //栈不为空且当前高度大于栈顶高度，当前山的高度比栈中的高（栈底的山最高）
            while (!stack.isEmpty() && arr[i] > stack.peek().height) {
                Mountain pop = stack.pop();
                sum = sum + pop.num * 2;
                //相同高等的山峰间也组成山峰对
                if (pop.num>1) {
                    sum = sum + pop.num * (pop.num -1 ) /2;
                }
            }
            if (!stack.isEmpty() && arr[i] == stack.peek().height) {
                stack.peek().num++;
            } else {
                stack.push(new Mountain(arr[i], 1));
            }
            i++;
            if (i==arr.length) i = 0;
        }

        while (!stack.isEmpty()) {

            if (stack.size()>2) {
                //如果栈中元素大于2，则说明比当前栈顶高的元素左右都有
                Mountain pop = stack.pop();
                sum = sum + pop.num * 2;
                if (pop.num>1) {
                    sum = sum + pop.num * (pop.num -1 ) /2;
                }
            } if (stack.size()==2) {
                //次高的山，如果栈底的山的数量大于1， 则次高的山左右都有更高的山峰
                Mountain pop = stack.pop();
                if (stack.peek().num>1) {
                    sum = sum + pop.num * 2;
                } else {
                    sum = sum + pop.num;
                    //如果次高的山峰数量大于1， 最高的山峰数量1，则次高之间也可以组成山峰对
                }
                if (pop.num>1) {
                    sum = sum + pop.num * (pop.num -1 ) /2;
                }
            } else {
                Mountain pop = stack.pop();
                //如果最高的山峰数量大于1，则最高之间也可以组成山峰对
                if (stack.peek().num>1) {
                    sum = sum + pop.num * (pop.num -1 ) /2;
                }
            }
        }
        return sum;
    }

    public static class Mountain {
        int height;
        //当前高度的山个数
        int num;
        Mountain(int height, int index) {
            this.height = height;
            this.num = index;
        }
    }
}
